package backtrack;
import java.util.ArrayList;
import java.util.List;

/**
 * @Description 面试题 08.04. 幂集 https://leetcode.cn/problems/power-set-lcci/
 * @Author Firenut
 * @Date 2023-01-22 14:47
 */
public class subsets {
    List<List<Integer>>ans=new ArrayList<>();
    List<Integer>list=new ArrayList<>();

    // 典型的回溯问题
    // 时间复杂度O(n * 2^n): 构造一个情况需要时间复杂度为O(n),一共有 2^n种情况
    // 空间复杂度O(n): 递归栈空间代价为O(n),使用list来存储每个状态的代价为O(n)
    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums,0);
        return ans;
    }

    void dfs(int[]nums,int index){
        if(index==nums.length){
            List<Integer> res = new ArrayList<>(list);
            ans.add(res);
            return;
        }

        //选当前索引的元素
        list.add(nums[index]);
        dfs(nums,index+1);

        //不选当前索引的元素
        list.remove(list.size()-1);
        dfs(nums,index+1);
    }
}